 /********************************************************************************************\
 * libeds - extensible data structures library                                                *
 * Copyright (C) 2006, Dan Kruchinin, <just.asgard@gmail.com>                                 *
 *                                                                                            *
 * -> test/rb_tree_test.c                                                                     *
 *                                                                                            *
 * This library is free software; you can redistribute it and/or modify it under the terms of *
 * the GNU Lesser General Public License as published by the Free Software Foundation;        *
 * either version 2.1 of the License, or (at your option) any later version.                  *
 *                                                                                            *
 * This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;  *
 * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  *
 * See the GNU Lesser General Public License for more details.                                *
 *                                                                                            *
 * You should have received a copy of the GNU Lesser General Public License along with this   *
 * library; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330,  *
 * Boston, MA 02111-1307 USA                                                                  *
 \********************************************************************************************/

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdarg.h>
#include "ds.h"
#include "safe_alloc.h"
#include "errors.h"
#include "trees/rb_tree.h"

#define MAX 16

void error(const char* msg, ...)
{
  va_list ap;

  va_start(ap, msg);
  vfprintf(stderr, msg, ap);
  va_end(ap);
  exit(EXIT_FAILURE);
}

void dump_tree(rb_tree* t, bit_node* n)
{
  if(node_empty(n)) {
    printf("[empty]\n");
    return;
  }

  if(node_empty(t->node_parent(n)))
    printf("ROOT:  ");
  else {
    if(t->node_left(t->node_parent(n)) == n)
      printf("LEFT:  ");
    else
      printf("RIGHT: ");
  }

  printf("k = [%s]; ", ((node_key(n) == NULL) ? "no key" : (char*)node_key(n)));
  printf("v = <%d>; nodes = %d; bh = %d; color is ", *((int*)node_value(n)), n->_nofnodes, t->node_get_bh(n));

  if(t->node_get_color(n) == RBT_CRED) {
    printf("{%s}", "red");
  }
  if(t->node_get_color(n) == RBT_CBLACK) {
    printf("{%s}", "black");
  }

  putchar('\n');
  
  dump_tree(t, t->node_left(n));
  dump_tree(t, t->node_right(n));
}

void dump_tree_info(rb_tree* rbt)
{
  int h;
  
  h = rbt->node_height(rbt->root(rbt->tree));
  printf("tree height is %d\n", h);
  h = rbt->node_ipl(rbt->root(rbt->tree));
  printf("tree internal path len is %d\n", h);
  h = rbt->node_epl(rbt->root(rbt->tree));
  printf("tree external path len is %d\n", h);
  h = rbt->node_get_bh(rbt->root(rbt->tree));
  printf("black height of tree is %d\n", h);  
}

int _copy_wk(bit_node* n, void* key, void* value)
{
  node_value(n) = smalloc(sizeof(int));
  *((int*)node_value(n)) = *((int*)value);

  return 0;
}

void _delete_wk(void* key, void* value)
{
  sfree(value);
}

ds_cmp_t _cmp_wk(const void* one, const void* two)
{
  int o, t;

  o = *((int*)one);
  t = *((int*)two);

  if(o > t)
	return DS_CMP_GRT;
  else if(o < t)
	return DS_CMP_LESS;
  else
	return DS_CMP_EQ;
}

int _copy(bit_node* n, void* key, void* value)
{
  size_t len = strlen((char*)key);
  
  node_value(n) = scalloc(1, sizeof(int));
  node_key(n) = scalloc(1, len + 1);

  *((int*)node_value(n)) = *((int*)value);
  strncpy((char*)node_key(n), (char*)key, len + 1);

  return 0;
}

void _delete(void* key, void* value)
{
  sfree(key);
  sfree(value);
}

ds_cmp_t _cmp(const void* one, const void* two)
{
  int res;

  res = strcmp((char*)one, (char*)two);

  if(res > 0)
    return DS_CMP_GRT;
  if(res < 0)
    return DS_CMP_LESS;

  return DS_CMP_EQ;
}

int main(void)
{
  rb_tree *rbt, *rbt0, *rbt_j;
  bit_node* tmp;
  int ins, h, c;

  if((rbt = rb_create()) == NULL) {
    printf("err: %s\n", ds_errmsg());
    exit(EXIT_FAILURE);
  }

  ds_reg_func(rbt->tree, _cmp, cmp);
  ds_reg_func(rbt->tree, _copy, copy);
  ds_reg_func(rbt->tree, _delete, delete);


  printf(":: New red-black tree:\n\n");
  
  ins = 121;
  if(rbt->insert(rbt->tree, "life", &ins) < 0)
	error("%s", ds_errmsg());
  ins = 22;
  if(rbt->insert(rbt->tree, "death", &ins) < 0)
	error("%s", ds_errmsg());
  ins = 8192;
  if(rbt->insert(rbt->tree, "nothing", &ins) < 0)
	error("%s", ds_errmsg());
  ins = 888;
  if(rbt->insert(rbt->tree, "thing", &ins) < 0)
	error("%s", ds_errmsg());
  ins = 234;
  if(rbt->insert(rbt->tree, "NULL", &ins) < 0)
	error("%s", ds_errmsg());
  ins = 5;
  if(rbt->insert(rbt->tree, "decadance", &ins) < 0)
	error("%s", ds_errmsg());
  ins = 3478;
  if(rbt->insert(rbt->tree, "pfff", &ins) < 0)
	error("%s", ds_errmsg());  
   
  dump_tree(rbt, rbt->root(rbt->tree));
  printf("\n\n");
  dump_tree_info(rbt);

  printf("\n\n:: Delete nodes with keys \"life\" and \"death\":\n\n");

  if((tmp = rbt->find(rbt->tree, "life")) == BIT_SEARCH_ERR)
	error("can't find element with key \"life\": %s", ds_errmsg());
  if(node_empty(tmp))
	error("element with key \"life\" doesn't found\n");

  rbt->delete(rbt->tree, tmp);

  if((tmp = rbt->find(rbt->tree, "death")) == BIT_SEARCH_ERR)
	error("can't find element with key \"death\": %s", ds_errmsg());
  if(node_empty(tmp))
	error("element with key \"death\" doesn't found\n");
	  
  rbt->delete(rbt->tree, tmp);
    
  dump_tree(rbt, rbt->root(rbt->tree));
  printf("\n\n");
  dump_tree_info(rbt);

  printf("\n\n:: Now we create another red-black tree:\n\n");
  rbt0 = rb_create();
  ds_reg_func(rbt0->tree, _cmp, cmp);
  ds_reg_func(rbt0->tree, _copy, copy);
  ds_reg_func(rbt0->tree, _delete, delete);
  
  ins = 75;
  if(rbt0->insert(rbt0->tree, "seventy five", &ins) < 0)
	error("%s", ds_errmsg());
  ins = 28;
  if(rbt0->insert(rbt0->tree, "twenty eight", &ins) < 0)
	error("%s", ds_errmsg());
  ins = 123;
  if(rbt0->insert(rbt0->tree, "one hundred twenty three", &ins) < 0)
	error("%s", ds_errmsg());
  ins = 8;
  if(rbt0->insert(rbt0->tree, "eight", &ins) < 0)
	error("%s", ds_errmsg());  

  dump_tree(rbt0, rbt0->root(rbt0->tree));
  printf("\n\n");
  dump_tree_info(rbt0);

  printf("\n\n:: Join both red-black trees in new one:\n\n");

  if((rbt_j = rb_join(rbt, rbt0)) == NULL)
	error("can't join two red-black trees: %s\n", ds_errmsg());

  dump_tree(rbt_j, rbt_j->root(rbt_j->tree));
  printf("\n\n");
  dump_tree_info(rbt_j);

  printf("\n\n:: So, I wan't to split main tree on two new. New tree will have root with key \"pfff\":\n\n");

  if((tmp = rbt_j->find(rbt_j->tree, "pfff")) == BIT_SEARCH_ERR)
	error("can't find node with key \"pfff\": %s\n", ds_errmsg());
  if(node_empty(tmp))
	error("node with key \"pfff\" doesn't exists!\n");
  if((rbt = rb_split(rbt_j, tmp)) == NULL)
	error("can't split tree: %s\n", ds_errmsg());

  printf("FIRTS TREE:\n");
  dump_tree(rbt_j, rbt_j->root(rbt_j->tree));
  printf("\n\n");
  dump_tree_info(rbt_j);

  printf("\n\nSECOND TREE:\n");
  dump_tree(rbt, rbt->root(rbt->tree));
  printf("\n\n");
  dump_tree_info(rbt);  


  printf("\n\n:: I want my tree has only uniqueue keys, so...:\n\n");
  ds_set_flags(rbt->tree, DS_FUK);

  ins = 234;
  if((h = rbt->insert(rbt->tree, "pfff", &ins)) < 0)
	fprintf(stderr, "can't insert node with key \"pfff\":[code %d] %s\n", ds_errcode(), ds_strerror(h));

  printf("\n\n:: Now I'll create tree without keys:\n\n");
  rbt0 = rb_create();
  ds_set_flags(rbt0->tree, DS_FNOKEYS);
  ds_reg_func(rbt0->tree, _cmp_wk, cmp);
  ds_reg_func(rbt0->tree, _copy_wk, copy);
  ds_reg_func(rbt0->tree, _delete_wk, delete);

  ins = 1;
  if(rbt0->insert(rbt0->tree, NULL, &ins) < 0)
	error("can't insert value %d: %s\n", ins);
  ins = 2;
  if(rbt0->insert(rbt0->tree, NULL, &ins) < 0)
	error("can't insert value %d: %s\n", ins);
  ins = 4;
  if(rbt0->insert(rbt0->tree, NULL, &ins) < 0)
	error("can't insert value %d: %s\n", ins);
  ins = 8;
  if(rbt0->insert(rbt0->tree, NULL, &ins) < 0)
	error("can't insert value %d: %s\n", ins);
  ins = 16;
  if(rbt0->insert(rbt0->tree, NULL, &ins) < 0)
	error("can't insert value %d: %s\n", ins);
  ins = 32;
  if(rbt0->insert(rbt0->tree, NULL, &ins) < 0)
	error("can't insert value %d: %s\n", ins);

  dump_tree(rbt0, rbt0->root(rbt0->tree));
  printf("\n\n");
  dump_tree_info(rbt0);

  printf("\n\n:: Now I'll try to make my tree without keys to hold only uniqueue values:\n\n");
  ds_set_flags(rbt0->tree, DS_FUK);
  ins = 1;
  if(rbt0->insert(rbt0->tree, NULL, &ins) < 0)
	fprintf(stderr, "can't insert \"%d\" in tree: %s\n", ins, ds_errmsg());
  ins = 65536;
  if(rbt0->insert(rbt0->tree, NULL, &ins) < 0)
	fprintf(stderr, "can't insert \"%d\" in tree: %s\n", ins, ds_errmsg());

  dump_tree(rbt0, rbt0->root(rbt0->tree));
  printf("\n\n");
  dump_tree_info(rbt0);  
  
  rb_destroy(rbt_j);
  rb_destroy(rbt);
  rb_destroy(rbt0);
  exit(EXIT_SUCCESS);
}

